1176B - Merge it - CodeForces Solution

//#define _GLIBCXX_DEBUG 1
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#define int               long long
#define lwr               lower_bound
#define upr               upper_bound
#define pb                push_back
#define ff                first
#define ss                second
#define nl                "\n"
#define go(x)			  {cout<<x<<nl; return;}
#define all(x)            x.begin(),x.end()
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define oset               tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>


const long long INF=1e18;
const long long mod=1e9+7;
const int nax=4e5+10;

int get_bit_count(int n){
	return __builtin_popcountll(n);
}

int binpow(int a,int b,int m){
    int res=1;
    while(b>0){
        if(b&1)
        {
		 	res=(res*(a%m))%m;
		 	b--;
        }
		else
		{
			a=((a%m)*(a%m))%m;
			b/=2;
		}
    }
    return res;
}

int mod_inv(int n, int p)
{
    return binpow(n, p - 2, p);
}

int gcd(int a,int b){
	if(b==0){return a;}
	return gcd(b,a%b);
}

vector<int> find_lps(string s){
	int n=s.size();
	vector<int> arr(n,0);
	for(int i=1;i<n;i++){
		int j=arr[i-1];
		while(j>0 && s[j]!=s[i]){
			j=arr[j-1];
		}
		if(s[j]==s[i]){
			j++;
		}
		arr[i]=j;
	}
	return arr;
}

class segtree
{
    public:
    	int size;
    	int n;
    	vector<int> seg;
    	void init(int k)
    	{
    		n=k;
    		size=1;
    		while(size<n) size*=2;
    		seg=vector<int>(2*size);
		}

		void merge(int & seg, int& left,int& right)
		{
			seg=left+right;
		}
		void build(int x, int lx,int rx,vector<int>& arr)
		{
			if(rx==lx+1)
			{
				if(lx<n) seg[x]=arr[lx];
				return;
			}
			int m=(lx+rx)/2;
			build(2*x+1,lx,m,arr);
			build(2*x+2,m,rx,arr);
			merge(seg[x],seg[2*x+1],seg[2*x+2]);
		}

		void build(vector<int>& arr){build(0,0,size,arr);}

		void set(int i, int v, int x, int lx, int rx)
		{
			if(rx==lx+1)
			{
				if(lx<n) seg[x]=v;
				return;
			}
			int m=(lx+rx)/2;
			if(i<m) set(i,v,2*x+1,lx,m);
			else set(i,v,2*x+2,m,rx);
			merge(seg[x],seg[2*x+1],seg[2*x+2]);
		}

		void set(int i, int v){set(i,v,0,0,size);}

		int find(int x, int lx, int rx, int l,int r)
		{
			if(rx<=l or lx>=r) return 0;
			if(lx>=l and rx<=r) return seg[x];
			int m=(lx+rx)/2;
			return find(2*x+1,lx,m,l,r)+find(2*x+2,m,rx,l,r);
		}

		int find(int l,int r){return find(0,0,size,l,r);}

};

bool isPrime(int n){
	if(n == 1) return false;
	for(int i = 2 ; i * i <= n ; i++){
		if(n % i == 0) return false;
	}

	return true;
}

int getFact(int n){
	int ans = INT_MAX;

	for(int i = 2 ; i * i <= n ; i++){
		if(n % i == 0){
			ans = min(ans , i);
			ans = min(n/i , ans);
		}
	}

	return ans;
}

	// int n;
	// cin>>n;

	// vector<int> v;

	// for(int i = 0 ; i< n ; i++){
	// 	int temp;
	// 	cin>>temp;
	// 	v.push_back(temp);
	// }

// You Got This.....

void testcase(int test)
{
	int n;
	cin>>n;

	vector<int> v;

	for(int i = 0 ; i< n ; i++){
		int temp;
		cin>>temp;
		v.push_back(temp);
	}

	int cnt0 = 0 , cnt1 = 0 , cnt2 = 0;

	for(int i = 0 ; i < n ; i++){
		if(v[i] % 3 == 0) cnt0++;
		if(v[i] % 3 == 1) cnt1++;
		if(v[i] % 3 == 2) cnt2++;
	}

	int ans = 0;
	ans += cnt0;

	ans += min(cnt1, cnt2);
	int x = min(cnt1, cnt2);
	cnt1 -= x;
	cnt2 -= x;

	ans += cnt1/3;
	ans += cnt2/3;

	cout<<ans<<"\n";
}


signed main(){
	IOS;
	int t=1;
	cin>>t;

	for(int i=1;i<=t;i++)
	{
		testcase(i);
	}
	return 0;
}